package chapter7.graph;

/**
 * Created by lili on 2017/7/1.
 */
//【例7.5】  以Floyd算法求带权图每对顶点间的最短路径。

public class WeightedDirectedG9                  //带权有向图G9
{
    public static void main(String args[])
    {
        String[] vertices={"A","B","C","D","E","F"};
        Edge edges[]={new Edge(0,1,13), new Edge(0,4,12),
                new Edge(1,3,18),
                new Edge(2,0,23),  new Edge(2,1,15), new Edge(2,5,29),
                new Edge(3,2,4), new Edge(3,4,5),
                new Edge(4,2,11), new Edge(4,5,31),
                new Edge(5,3,17)};
        AdjMatrixGraph<String> graph = new AdjMatrixGraph<String>(vertices, edges);
        System.out.print("带权有向图G9，"+graph.toString());
//        for (int i=0; i<graph.vertexCount(); i++)
//        graph.shortestPath(i);               //顶点vi的单源最短路径，Dijkstra算法
        graph.shortestPath();                    //调用Floyd算法求带权图每对顶点间的最短路径
    }
}
/*
程序运行结果如下：
  //Dijkstra算法
带权有向图G9，顶点集合：(A, B, C, D, E, F)
邻接矩阵:
  0  13  ∞  ∞  12  ∞
  ∞  0  ∞  18  ∞  ∞
  23  15  0  ∞  ∞  29
  ∞  ∞  4  0  5  ∞
  ∞  ∞  11  ∞  0  31
  ∞  ∞  ∞  17  ∞  0

vset数组{1,0,0,0,0,0}	path数组{-1,0,-1,-1,0,-1}	dist数组{0,13,∞,∞,12,∞}
vset数组{1,0,0,0,1,0}	path数组{-1,0,4,-1,0,4}	dist数组{0,13,23,∞,12,43}
vset数组{1,1,0,0,1,0}	path数组{-1,0,4,1,0,4}	dist数组{0,13,23,31,12,43}
vset数组{1,1,1,0,1,0}	path数组{-1,0,4,1,0,4}	dist数组{0,13,23,31,12,43}
vset数组{1,1,1,1,1,0}	path数组{-1,0,4,1,0,4}	dist数组{0,13,23,31,12,43}
vset数组{1,1,1,1,1,1}	path数组{-1,0,4,1,0,4}	dist数组{0,13,23,31,12,43}
从顶点A到其他顶点的最短路径如下：
(A,B)长度为13
(A,E,C)长度为23
(A,B,D)长度为31
(A,E)长度为12
(A,E,F)长度为43

vset数组{0,1,0,0,0,0}	path数组{-1,-1,-1,1,-1,-1}	dist数组{∞,0,∞,18,∞,∞}
vset数组{0,1,0,1,0,0}	path数组{-1,-1,3,1,3,-1}	dist数组{∞,0,22,18,23,∞}
vset数组{0,1,1,1,0,0}	path数组{2,-1,3,1,3,2}	dist数组{45,0,22,18,23,51}
vset数组{0,1,1,1,1,0}	path数组{2,-1,3,1,3,2}	dist数组{45,0,22,18,23,51}
vset数组{1,1,1,1,1,0}	path数组{2,-1,3,1,3,2}	dist数组{45,0,22,18,23,51}
vset数组{1,1,1,1,1,1}	path数组{2,-1,3,1,3,2}	dist数组{45,0,22,18,23,51}
从顶点B到其他顶点的最短路径如下：
(B,D,C,A)长度为45
(B,D,C)长度为22
(B,D)长度为18
(B,D,E)长度为23
(B,D,C,F)长度为51

vset数组{0,0,1,0,0,0}	path数组{2,2,-1,-1,-1,2}	dist数组{23,15,0,∞,∞,29}
vset数组{0,1,1,0,0,0}	path数组{2,2,-1,1,-1,2}	dist数组{23,15,0,33,∞,29}
vset数组{1,1,1,0,0,0}	path数组{2,2,-1,1,0,2}	dist数组{23,15,0,33,35,29}
vset数组{1,1,1,0,0,1}	path数组{2,2,-1,1,0,2}	dist数组{23,15,0,33,35,29}
vset数组{1,1,1,1,0,1}	path数组{2,2,-1,1,0,2}	dist数组{23,15,0,33,35,29}
vset数组{1,1,1,1,1,1}	path数组{2,2,-1,1,0,2}	dist数组{23,15,0,33,35,29}
从顶点C到其他顶点的最短路径如下：
(C,A)长度为23
(C,B)长度为15
(C,B,D)长度为33
(C,A,E)长度为35
(C,F)长度为29

vset数组{0,0,0,1,0,0}	path数组{-1,-1,3,-1,3,-1}	dist数组{∞,∞,4,0,5,∞}
vset数组{0,0,1,1,0,0}	path数组{2,2,3,-1,3,2}	dist数组{27,19,4,0,5,33}
vset数组{0,0,1,1,1,0}	path数组{2,2,3,-1,3,2}	dist数组{27,19,4,0,5,33}
vset数组{0,1,1,1,1,0}	path数组{2,2,3,-1,3,2}	dist数组{27,19,4,0,5,33}
vset数组{1,1,1,1,1,0}	path数组{2,2,3,-1,3,2}	dist数组{27,19,4,0,5,33}
vset数组{1,1,1,1,1,1}	path数组{2,2,3,-1,3,2}	dist数组{27,19,4,0,5,33}
从顶点D到其他顶点的最短路径如下：
(D,C,A)长度为27
(D,C,B)长度为19
(D,C)长度为4
(D,E)长度为5
(D,C,F)长度为33

vset数组{0,0,0,0,1,0}	path数组{-1,-1,4,-1,-1,4}	dist数组{∞,∞,11,∞,0,31}
vset数组{0,0,1,0,1,0}	path数组{2,2,4,-1,-1,4}	dist数组{34,26,11,∞,0,31}
vset数组{0,1,1,0,1,0}	path数组{2,2,4,1,-1,4}	dist数组{34,26,11,44,0,31}
vset数组{0,1,1,0,1,1}	path数组{2,2,4,1,-1,4}	dist数组{34,26,11,44,0,31}
vset数组{1,1,1,0,1,1}	path数组{2,2,4,1,-1,4}	dist数组{34,26,11,44,0,31}
vset数组{1,1,1,1,1,1}	path数组{2,2,4,1,-1,4}	dist数组{34,26,11,44,0,31}
从顶点E到其他顶点的最短路径如下：
(E,C,A)长度为34
(E,C,B)长度为26
(E,C)长度为11
(E,C,B,D)长度为44
(E,F)长度为31

vset数组{0,0,0,0,0,1}	path数组{-1,-1,-1,5,-1,-1}	dist数组{∞,∞,∞,17,∞,0}
vset数组{0,0,0,1,0,1}	path数组{-1,-1,3,5,3,-1}	dist数组{∞,∞,21,17,22,0}
vset数组{0,0,1,1,0,1}	path数组{2,2,3,5,3,-1}	dist数组{44,36,21,17,22,0}
vset数组{0,0,1,1,1,1}	path数组{2,2,3,5,3,-1}	dist数组{44,36,21,17,22,0}
vset数组{0,1,1,1,1,1}	path数组{2,2,3,5,3,-1}	dist数组{44,36,21,17,22,0}
vset数组{1,1,1,1,1,1}	path数组{2,2,3,5,3,-1}	dist数组{44,36,21,17,22,0}
从顶点F到其他顶点的最短路径如下：
(F,D,C,A)长度为44
(F,D,C,B)长度为36
(F,D,C)长度为21
(F,D)长度为17
(F,D,E)长度为22


*/
/*Floyd算法
带权有向图G9，顶点集合：(A, B, C, D, E, F)
邻接矩阵:
  0  13  ∞  ∞  12  ∞
  ∞  0  ∞  18  ∞  ∞
  23  15  0  ∞  ∞  29
  ∞  ∞  4  0  5  ∞
  ∞  ∞  11  ∞  0  31
  ∞  ∞  ∞  17  ∞  0
初值path数组
  -1  0  -1  -1  0  -1
  -1  -1  -1  1  -1  -1
  2  2  -1  -1  -1  2
  -1  -1  3  -1  3  -1
  -1  -1  4  -1  -1  4
  -1  -1  -1  5  -1  -1
dist数组
  0  13  ∞  ∞  12  ∞
  ∞  0  ∞  18  ∞  ∞
  23  15  0  ∞  ∞  29
  ∞  ∞  4  0  5  ∞
  ∞  ∞  11  ∞  0  31
  ∞  ∞  ∞  17  ∞  0

以A作为中间顶点
(B,C)路径长度99999，替换为(B,A),(A,C)路径长度199998？否
(B,D)路径长度18，替换为(B,A),(A,D)路径长度199998？否
(B,E)路径长度99999，替换为(B,A),(A,E)路径长度100011？否
(B,F)路径长度99999，替换为(B,A),(A,F)路径长度199998？否
(C,B)路径长度15，替换为(C,A),(A,B)路径长度36？否
(C,D)路径长度99999，替换为(C,A),(A,D)路径长度100022？否
(C,E)路径长度99999，替换为(C,A),(A,E)路径长度35？是，d24=35，p24=0
(C,F)路径长度29，替换为(C,A),(A,F)路径长度100022？否
(D,B)路径长度99999，替换为(D,A),(A,B)路径长度100012？否
(D,C)路径长度4，替换为(D,A),(A,C)路径长度199998？否
(D,E)路径长度5，替换为(D,A),(A,E)路径长度100011？否
(D,F)路径长度99999，替换为(D,A),(A,F)路径长度199998？否
(E,B)路径长度99999，替换为(E,A),(A,B)路径长度100012？否
(E,C)路径长度11，替换为(E,A),(A,C)路径长度199998？否
(E,D)路径长度99999，替换为(E,A),(A,D)路径长度199998？否
(E,F)路径长度31，替换为(E,A),(A,F)路径长度199998？否
(F,B)路径长度99999，替换为(F,A),(A,B)路径长度100012？否
(F,C)路径长度99999，替换为(F,A),(A,C)路径长度199998？否
(F,D)路径长度17，替换为(F,A),(A,D)路径长度199998？否
(F,E)路径长度99999，替换为(F,A),(A,E)路径长度100011？否
path数组
  -1  0  -1  -1  0  -1
  -1  -1  -1  1  -1  -1
  2  2  -1  -1  0  2
  -1  -1  3  -1  3  -1
  -1  -1  4  -1  -1  4
  -1  -1  -1  5  -1  -1
dist数组
  0  13  ∞  ∞  12  ∞
  ∞  0  ∞  18  ∞  ∞
  23  15  0  ∞  35  29
  ∞  ∞  4  0  5  ∞
  ∞  ∞  11  ∞  0  31
  ∞  ∞  ∞  17  ∞  0

以B作为中间顶点
(A,C)路径长度99999，替换为(A,B),(B,C)路径长度100012？否
(A,D)路径长度99999，替换为(A,B),(B,D)路径长度31？是，d03=31，p03=1
(A,E)路径长度12，替换为(A,B),(B,E)路径长度100012？否
(A,F)路径长度99999，替换为(A,B),(B,F)路径长度100012？否
(C,A)路径长度23，替换为(C,B),(B,A)路径长度100014？否
(C,D)路径长度99999，替换为(C,B),(B,D)路径长度33？是，d23=33，p23=1
(C,A,E)路径长度35，替换为(C,B),(B,E)路径长度100014？否
(C,F)路径长度29，替换为(C,B),(B,F)路径长度100014？否
(D,A)路径长度99999，替换为(D,B),(B,A)路径长度199998？否
(D,C)路径长度4，替换为(D,B),(B,C)路径长度199998？否
(D,E)路径长度5，替换为(D,B),(B,E)路径长度199998？否
(D,F)路径长度99999，替换为(D,B),(B,F)路径长度199998？否
(E,A)路径长度99999，替换为(E,B),(B,A)路径长度199998？否
(E,C)路径长度11，替换为(E,B),(B,C)路径长度199998？否
(E,D)路径长度99999，替换为(E,B),(B,D)路径长度100017？否
(E,F)路径长度31，替换为(E,B),(B,F)路径长度199998？否
(F,A)路径长度99999，替换为(F,B),(B,A)路径长度199998？否
(F,C)路径长度99999，替换为(F,B),(B,C)路径长度199998？否
(F,D)路径长度17，替换为(F,B),(B,D)路径长度100017？否
(F,E)路径长度99999，替换为(F,B),(B,E)路径长度199998？否
path数组
  -1  0  -1  1  0  -1
  -1  -1  -1  1  -1  -1
  2  2  -1  1  0  2
  -1  -1  3  -1  3  -1
  -1  -1  4  -1  -1  4
  -1  -1  -1  5  -1  -1
dist数组
  0  13  ∞  31  12  ∞
  ∞  0  ∞  18  ∞  ∞
  23  15  0  33  35  29
  ∞  ∞  4  0  5  ∞
  ∞  ∞  11  ∞  0  31
  ∞  ∞  ∞  17  ∞  0

以C作为中间顶点
(A,B)路径长度13，替换为(A,C),(C,B)路径长度100014？否
(A,B,D)路径长度31，替换为(A,C),(C,B,D)路径长度100032？否
(A,E)路径长度12，替换为(A,C),(C,A,E)路径长度100034？否
(A,F)路径长度99999，替换为(A,C),(C,F)路径长度100028？否
(B,A)路径长度99999，替换为(B,C),(C,A)路径长度100022？否
(B,D)路径长度18，替换为(B,C),(C,B,D)路径长度100032？否
(B,E)路径长度99999，替换为(B,C),(C,A,E)路径长度100034？否
(B,F)路径长度99999，替换为(B,C),(C,F)路径长度100028？否
(D,A)路径长度99999，替换为(D,C),(C,A)路径长度27？是，d30=27，p30=2
(D,B)路径长度99999，替换为(D,C),(C,B)路径长度19？是，d31=19，p31=2
(D,E)路径长度5，替换为(D,C),(C,A,E)路径长度39？否
(D,F)路径长度99999，替换为(D,C),(C,F)路径长度33？是，d35=33，p35=2
(E,A)路径长度99999，替换为(E,C),(C,A)路径长度34？是，d40=34，p40=2
(E,B)路径长度99999，替换为(E,C),(C,B)路径长度26？是，d41=26，p41=2
(E,D)路径长度99999，替换为(E,C),(C,B,D)路径长度44？是，d43=44，p43=1
(E,F)路径长度31，替换为(E,C),(C,F)路径长度40？否
(F,A)路径长度99999，替换为(F,C),(C,A)路径长度100022？否
(F,B)路径长度99999，替换为(F,C),(C,B)路径长度100014？否
(F,D)路径长度17，替换为(F,C),(C,B,D)路径长度100032？否
(F,E)路径长度99999，替换为(F,C),(C,A,E)路径长度100034？否
path数组
  -1  0  -1  1  0  -1
  -1  -1  -1  1  -1  -1
  2  2  -1  1  0  2
  2  2  3  -1  3  2
  2  2  4  1  -1  4
  -1  -1  -1  5  -1  -1
dist数组
  0  13  ∞  31  12  ∞
  ∞  0  ∞  18  ∞  ∞
  23  15  0  33  35  29
  27  19  4  0  5  33
  34  26  11  44  0  31
  ∞  ∞  ∞  17  ∞  0

以D作为中间顶点
(A,B)路径长度13，替换为(A,B,D),(D,C,B)路径长度50？否
(A,C)路径长度99999，替换为(A,B,D),(D,C)路径长度35？是，d02=35，p02=3
(A,E)路径长度12，替换为(A,B,D),(D,E)路径长度36？否
(A,F)路径长度99999，替换为(A,B,D),(D,C,F)路径长度64？是，d05=64，p05=2
(B,A)路径长度99999，替换为(B,D),(D,C,A)路径长度45？是，d10=45，p10=2
(B,C)路径长度99999，替换为(B,D),(D,C)路径长度22？是，d12=22，p12=3
(B,E)路径长度99999，替换为(B,D),(D,E)路径长度23？是，d14=23，p14=3
(B,F)路径长度99999，替换为(B,D),(D,C,F)路径长度51？是，d15=51，p15=2
(C,A)路径长度23，替换为(C,B,D),(D,C,A)路径长度60？否
(C,B)路径长度15，替换为(C,B,D),(D,C,B)路径长度52？否
(C,A,E)路径长度35，替换为(C,B,D),(D,E)路径长度38？否
(C,F)路径长度29，替换为(C,B,D),(D,C,F)路径长度66？否
(E,C,A)路径长度34，替换为(E,C,B,D),(D,C,A)路径长度71？否
(E,C,B)路径长度26，替换为(E,C,B,D),(D,C,B)路径长度63？否
(E,C)路径长度11，替换为(E,C,B,D),(D,C)路径长度48？否
(E,F)路径长度31，替换为(E,C,B,D),(D,C,F)路径长度77？否
(F,A)路径长度99999，替换为(F,D),(D,C,A)路径长度44？是，d50=44，p50=2
(F,B)路径长度99999，替换为(F,D),(D,C,B)路径长度36？是，d51=36，p51=2
(F,C)路径长度99999，替换为(F,D),(D,C)路径长度21？是，d52=21，p52=3
(F,E)路径长度99999，替换为(F,D),(D,E)路径长度22？是，d54=22，p54=3
path数组
  -1  0  3  1  0  2
  2  -1  3  1  3  2
  2  2  -1  1  0  2
  2  2  3  -1  3  2
  2  2  4  1  -1  4
  2  2  3  5  3  -1
dist数组
  0  13  35  31  12  64
  45  0  22  18  23  51
  23  15  0  33  35  29
  27  19  4  0  5  33
  34  26  11  44  0  31
  44  36  21  17  22  0

以E作为中间顶点
(A,B)路径长度13，替换为(A,E),(E,C,B)路径长度38？否
(A,B,D,C)路径长度35，替换为(A,E),(E,C)路径长度23？是，d02=23，p02=4
(A,B,D)路径长度31，替换为(A,E),(E,C,B,D)路径长度56？否
(A,E,C,F)路径长度64，替换为(A,E),(E,F)路径长度43？是，d05=43，p05=4
(B,D,C,A)路径长度45，替换为(B,D,E),(E,C,A)路径长度57？否
(B,D,C)路径长度22，替换为(B,D,E),(E,C)路径长度34？否
(B,D)路径长度18，替换为(B,D,E),(E,C,B,D)路径长度67？否
(B,D,C,F)路径长度51，替换为(B,D,E),(E,F)路径长度54？否
(C,A)路径长度23，替换为(C,A,E),(E,C,A)路径长度69？否
(C,B)路径长度15，替换为(C,A,E),(E,C,B)路径长度61？否
(C,B,D)路径长度33，替换为(C,A,E),(E,C,B,D)路径长度79？否
(C,F)路径长度29，替换为(C,A,E),(E,F)路径长度66？否
(D,C,A)路径长度27，替换为(D,E),(E,C,A)路径长度39？否
(D,C,B)路径长度19，替换为(D,E),(E,C,B)路径长度31？否
(D,C)路径长度4，替换为(D,E),(E,C)路径长度16？否
(D,C,F)路径长度33，替换为(D,E),(E,F)路径长度36？否
(F,D,C,A)路径长度44，替换为(F,D,E),(E,C,A)路径长度56？否
(F,D,C,B)路径长度36，替换为(F,D,E),(E,C,B)路径长度48？否
(F,D,C)路径长度21，替换为(F,D,E),(E,C)路径长度33？否
(F,D)路径长度17，替换为(F,D,E),(E,C,B,D)路径长度66？否
path数组
  -1  0  4  1  0  4
  2  -1  3  1  3  2
  2  2  -1  1  0  2
  2  2  3  -1  3  2
  2  2  4  1  -1  4
  2  2  3  5  3  -1
dist数组
  0  13  23  31  12  43
  45  0  22  18  23  51
  23  15  0  33  35  29
  27  19  4  0  5  33
  34  26  11  44  0  31
  44  36  21  17  22  0

以F作为中间顶点
(A,B)路径长度13，替换为(A,E,F),(F,D,C,B)路径长度79？否
(A,E,C)路径长度23，替换为(A,E,F),(F,D,C)路径长度64？否
(A,B,D)路径长度31，替换为(A,E,F),(F,D)路径长度60？否
(A,E)路径长度12，替换为(A,E,F),(F,D,E)路径长度65？否
(B,D,C,A)路径长度45，替换为(B,D,C,F),(F,D,C,A)路径长度95？否
(B,D,C)路径长度22，替换为(B,D,C,F),(F,D,C)路径长度72？否
(B,D)路径长度18，替换为(B,D,C,F),(F,D)路径长度68？否
(B,D,E)路径长度23，替换为(B,D,C,F),(F,D,E)路径长度73？否
(C,A)路径长度23，替换为(C,F),(F,D,C,A)路径长度73？否
(C,B)路径长度15，替换为(C,F),(F,D,C,B)路径长度65？否
(C,B,D)路径长度33，替换为(C,F),(F,D)路径长度46？否
(C,A,E)路径长度35，替换为(C,F),(F,D,E)路径长度51？否
(D,C,A)路径长度27，替换为(D,C,F),(F,D,C,A)路径长度77？否
(D,C,B)路径长度19，替换为(D,C,F),(F,D,C,B)路径长度69？否
(D,C)路径长度4，替换为(D,C,F),(F,D,C)路径长度54？否
(D,E)路径长度5，替换为(D,C,F),(F,D,E)路径长度55？否
(E,C,A)路径长度34，替换为(E,F),(F,D,C,A)路径长度75？否
(E,C,B)路径长度26，替换为(E,F),(F,D,C,B)路径长度67？否
(E,C)路径长度11，替换为(E,F),(F,D,C)路径长度52？否
(E,C,B,D)路径长度44，替换为(E,F),(F,D)路径长度48？否
path数组
  -1  0  4  1  0  4
  2  -1  3  1  3  2
  2  2  -1  1  0  2
  2  2  3  -1  3  2
  2  2  4  1  -1  4
  2  2  3  5  3  -1
dist数组
  0  13  23  31  12  43
  45  0  22  18  23  51
  23  15  0  33  35  29
  27  19  4  0  5  33
  34  26  11  44  0  31
  44  36  21  17  22  0

每对顶点间的最短路径如下：
(A,B)长度为13
(A,E,C)长度为23
(A,B,D)长度为31
(A,E)长度为12
(A,E,F)长度为43
(B,D,C,A)长度为45
(B,D,C)长度为22
(B,D)长度为18
(B,D,E)长度为23
(B,D,C,F)长度为51
(C,A)长度为23
(C,B)长度为15
(C,B,D)长度为33
(C,A,E)长度为35
(C,F)长度为29
(D,C,A)长度为27
(D,C,B)长度为19
(D,C)长度为4
(D,E)长度为5
(D,C,F)长度为33
(E,C,A)长度为34
(E,C,B)长度为26
(E,C)长度为11
(E,C,B,D)长度为44
(E,F)长度为31
(F,D,C,A)长度为44
(F,D,C,B)长度为36
(F,D,C)长度为21
(F,D)长度为17
(F,D,E)长度为22

*/


